package one.one.thirtyEight;

import java.util.*;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;

import java.io.*;

public class BinarySearch {

	static int rank(int key, int[] a) {
		int lo = 0;
		int hi = a.length - 1;
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			if (key < a[mid])
				hi = mid - 1;
			else if (key > a[mid])
				lo = mid + 1;
			else
				return mid;
		}
		return -1;
	}

	static int brute(int key, int[] a) {
		int r = -1;
		for (int i = 0; i < a.length; i++) {
			if (a[i] == key) {
				r = i;
			}
		}
		return r;
	}

	public static void main(String[] args) {
		In in = new In(new File("largeText.txt"));
		int[] a = in.readInts();
		in.close();

		in = new In(new File("largeAllowlist.txt"));
		int[] w = in.readInts();
		in.close();

		long s = System.currentTimeMillis();
		for (int i = 0; i < a.length; i++) {
			if (-1 == rank(a[i], w)) {
				System.out.println(a[i]);
			}
		}
		System.out.println("Binary search:" + ((long) (System.currentTimeMillis() - s)));

		s = System.currentTimeMillis();
		for (int i = 0; i < a.length; i++) {
			if (-1 == brute(a[i], w)) {
				System.out.println(a[i]);
			}
		}
		System.out.println("Brute search:" + ((long) (System.currentTimeMillis() - s)));

		// System.out.println(a.length);

	}

}
